1. Field of the Invention
The present invention relates to a method of placing map data into a database. The present invention further relates to searching a map database to find objects within a given location and to find objects nearest a given location.
2. Description of the Background Art
Electronic maps typically store data identifying geographic areas along with data identifying objects referenced to the geographic areas. Objects identified in the map can include restaurants, gas stations, hotels, camp grounds, post offices, grocery stores and other places which a traveler may desire to locate in a geographic area.
For a map area of any significant extent, the object data can occupy hundreds of megabytes of memory space. In order to hold such vast quantities of map data economically, map data is typically stored on storage devices such as CD-ROMs or hard drives. To allow ease of locating particular data, the geographic data is typically divided into blocks, and data for each block is then separately stored in a storage device. Individual data blocks are typically linked by additional data to form a tree type structure with individual data blocks identified at the bottom of the tree, and groups of data blocks linked together farther up the tree, the groups progressing up the tree linking more data blocks until the top of the tree is reached where all data blocks of a map are linked together. With such a tree structure identifying and linking data blocks, if a user desires to access data in an area covering multiple data blocks, the data can be easily retrieved.
Objects are typically stored in the data blocks in the database in relation to their geographic location on a map. Thus, if a new object is added to a map, the new object data must be stored in a particular location within a block of data. Because of space limitations on a CD-ROM or hard drive, if a block of data with the newly added object becomes too large for the area of the storage device in which it is allocated, the block of data may be divided into two blocks. One of the separated blocks may then need to be located in a totally different area of the storage device. Such a change in data blocks can increase access time when locating data.
An example of a user request for data in the data blocks might be a request to find all post offices within a five square mile area. A conventional method used to find such objects would be to access the data blocks, starting with data at the top of the tree and proceeding down the tree to narrow the number of blocks requested until all data blocks are identified covering the five square mile area. All objects in the located data blocks are then retrieved from memory and their location from the current position of the user are calculated based on stored coordinates for each object. Objects which are outside the desired area are then typically discarded, and the remaining objects which are within the five square mile area can be displayed.
A request to find the nearest post office to the users current location typically proceeds in a similar manner. First, one or more data blocks are retrieved from memory which include the users current location, and all objects identifying post offices within the one or more blocks are identified. If the data blocks originally retrieved do not include any of the desired objects, additional data blocks are retrieved surrounding the originally retrieved data blocks and the search repeated until objects are located. Coordinates of located objects are then used to determine which object is the closest to the user.
With objects occupying as much as eight kilobytes each, a search through blocks of data to obtain object data can take a significant amount of time. Further, with a significant number of objects located in blocks identified in a search, calculations to determine which objects are within a given area, or which objects are closest to a users location can take a significant amount of time.